package leetcode.L500;

import java.util.Deque;
import java.util.LinkedList;

public class EX321 {
    public static void main(String[] args) {
        int[] nums1 = {5,6,8};
        int[] nums2 = {6,4,0};
        int k = 3;

        int[] ett = maxnum(nums1,1);

        int[] max = new int[k];
        int l1 = nums1.length;
        int l2 = nums2.length;
        for (int i = 0; i <= k&&i<=l1 ; i++) {
            int j = k-i;
            if(j>l2){
                continue;
            }
            int[] ew = maxnum(nums1,i);
            int[] ew2 = maxnum(nums2,j);
            int[] r = merge(ew,ew2);
            max = compare(max,r);
        }
        System.out.println(max);

    }
    public static int[] compare(int[] nums,int[] nums2){
        int l = nums.length;
        for (int i = 0; i < l ; i++) {
            if (nums[i]==nums2[i]){
                continue;
            }
            else if (nums[i]>nums2[i]){
                return nums;
            }
            else if(nums[i]<nums2[i]){
                return nums2;
            }
        }
        return nums;
    }


    public static int[] maxnum(int[] nums,int k){
        //nums指输入的数组，k需要存在的个数
        int[] zero = new int[0];
        if(k==0){
            return zero;
        }
        Deque<Integer> deque = new LinkedList<>();
        k = nums.length-k;

        for (int i = 0; i < nums.length ; i++) {
            int tep = nums[i];
            while (!deque.isEmpty()&&k>0&&deque.peekLast()<tep){
                deque.pollLast();
                k--;
            }
            deque.addLast(tep);
        }
        for (int i = 0; i < k ; i++) {
            deque.pollLast();
        }

        int si = deque.size();
        int[] res = new int[si];
        for (int j = 0; j < si ; j++) {
            res[j] = deque.pollFirst();
        }
        return res;
    }
    public static int[] merge(int[] nums1,int[] nums2){
        int l = nums1.length;
        int l2 = nums2.length;

        int[] res = new int[l+l2];

        int f=0,s=0;
        for (int i = 0; i < l+l2; i++) {
            if(s<l2&&f<l&&nums1[f]>nums2[s]){
                res[i] = nums1[f];
                f++;
                continue;
            }
            else if(f<l&&s<l2&&nums1[f]<nums2[s]){
                res[i] = nums2[s];
                s++;
                continue;
            }
            else if(s<l2&&f<l&&nums1[f]==nums2[s]){
                int ts =s;
                int tf =f;
                while(tf<l&&ts<l2&&nums1[tf]==nums2[ts]){
                    tf++;
                    ts++;
                }
                if(ts<l2&&(tf>=l||nums1[tf]<nums2[ts])){
                    res[i] = nums2[s];
                    s++;
                    continue;
                }
                else if(tf<l&&(ts>=l2||nums1[tf]>nums2[ts])){
                    res[i] = nums1[f];
                    f++;
                    continue;
                }
            }
            if(f>=l&&s<l2){
                res[i] = nums2[s];
                s++;
            }
            else if(f<l&&s>=l2){
                res[i] = nums1[f];
                f++;
            }
        }
        return res;
    }
}
